#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
		val(x), left(NULL), right(NULL) {
	}
};


vector<vector<int> > Print(TreeNode* pRoot) {
	vector<vector<int> > re;
	if (pRoot == NULL)
		return re;
	
	queue<TreeNode *> nodeQ;
	nodeQ.push(pRoot);
	bool ch = true;
	while (!nodeQ.empty())
	{
		vector<int> v;
		int size = nodeQ.size();
		for (int i = 0; i < size; ++i)
		{
			TreeNode *node = nodeQ.front();
			if (ch)
				v.push_back(node->val);
			else
				v.insert(v.begin(), node->val);
			
			if (node->left != NULL)
				nodeQ.push(node->left);
			if (node->right != NULL)
				nodeQ.push(node->right);
			nodeQ.pop();
		}
		re.push_back(v);
		ch = !ch;
	}
	return re;
}

vector<vector<int> > Print2(TreeNode* pRoot) {
	vector<vector<int> > re;
	if (pRoot == NULL)
		return re;

	queue<TreeNode *> nodeQ;
	nodeQ.push(pRoot);
	while (!nodeQ.empty())
	{
		int size = nodeQ.size();
		vector<int> v;
		for (int i = 0; i < size; ++i)
		{
			TreeNode *node = nodeQ.front();
			v.push_back(node->val);
			if (node->left != NULL)
				nodeQ.push(node->left);
			if (node->right != NULL)
				nodeQ.push(node->right);
			nodeQ.pop();
		}
		re.insert(re.begin(), v);
	}
	return re;
}

int main()
{
	TreeNode *root = new TreeNode(66);
	TreeNode *p = root;
	int i = 0;
	for (int j = 0; j < 10; ++j)
	{
	TreeNode *temp = new TreeNode(++i);
	p->left = temp;
	temp = new TreeNode(++i);
	p->right = temp;
	if (i % 3)
		p = p->left;
	else
		p = p->right;
	}
	vector<vector<int> > v = Print2(root);
	for (auto i : v)
	{
		for (auto j : i)
			cout << j << " ";
		cout << endl;
	}
	system("pause");
	return 0;
}